home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / DELPHI / EZDSL200.ZIP / EZDSLCOL.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1996-03-13  |  23.5 KB  |  856 lines
  1. {===EZDSLCOL==========================================================
  2.  
  3. Part of the EZ Delphi Structures Library--the collection classes.
  4.  
  5. EZDSLCOL is Copyright (c) 1995, 1996 by  Julian M. Bucknall
  6.  
  7. VERSION HISTORY
  8. 13Mar96 JMB 2.00 release for Delphi 2.0
  9. 18Jun95 JMB 1.00 initial release
  10. ======================================================================}
  11. { Copyright (c) 1995, 1996, Julian M. Bucknall. All Rights Reserved   }
  12.  
  13. unit EZDSLCol;
  14.  
  15. {$I EZDSLDEF.INC}
  16. {---Place any compiler options you require here-----------------------}
  17.  
  18.  
  19. {---------------------------------------------------------------------}
  20. {$I EZDSLOPT.INC}
  21.  
  22. interface
  23.  
  24. uses
  25.   SysUtils,
  26.   {$IFDEF Win32}
  27.   Windows,
  28.   {$ELSE}
  29.   WinTypes,
  30.   WinProcs,
  31.   {$ENDIF}
  32.   Classes,
  33.   EZDSLCts,
  34.   EZDSLSup,
  35.   EZDSLBse;
  36.  
  37. const
  38.   ezcPageElementCount = 92;
  39.   ezcPageArrayElementCount = 10922;
  40.   ezcMaxCount = ezcPageElementCount * ezcPageArrayElementCount;
  41.  
  42.   coIndexError = -1;
  43.   coOverflow   = -2;
  44.  
  45. type
  46.   PezcPage = ^TezcPage;
  47.   TezcPage = array [0..pred(ezcPageElementCount)] of pointer;
  48.  
  49.   PezcPageItem = ^TezcPageItem;
  50.   TezcPageItem = record
  51.     UsedItems : integer;
  52.     Items     : PezcPage;
  53.   end;
  54.  
  55.   PezcPageArray = ^TezcPageArray;
  56.   TezcPageArray = array [0..pred(ezcPageArrayElementCount)] of TezcPageItem;
  57.  
  58.   TEZCollection = class(TAbstractContainer)
  59.     private
  60.       PA : PezcPageArray;
  61.       SizeOfPA : Cardinal;
  62.       ItemsInPA : integer;
  63.       MaxItemsInPA : integer;
  64.  
  65.       CacheIndex     : longint;
  66.       CachePageNum   : integer;
  67.       CacheInxInPage : integer;
  68.  
  69.     protected
  70.       function GetLimit : longint;
  71.  
  72.       procedure AddPageItem(AtIndex : integer);
  73.       procedure DeletePageItem(AtIndex : integer);
  74.       function  GetPageGivenIndex(Index : longint;
  75.                                   var InxInPage : integer) : integer;
  76.       procedure GrowPageArray(NewNumElements : integer);
  77.       procedure ValidateIndex(Index : longint);
  78.  
  79.     public
  80.       constructor Create(DataOwner : boolean); override;
  81.       constructor Clone(Source : TAbstractContainer;
  82.                         DataOwner : boolean; NewCompare : TCompareFunc); override;
  83.       destructor Destroy; override;
  84.  
  85.       procedure Assign(Source : TPersistent); override;
  86.  
  87.       procedure Empty; override;
  88.  
  89.       function  At(Index : longint) : pointer;
  90.       procedure AtDelete(Index : longint);
  91.       procedure AtFree(Index : longint);
  92.       procedure AtInsert(Index : longint; Item : pointer);
  93.       procedure AtPut(Index : longint; Item : pointer);
  94.       procedure Delete(Item : pointer);
  95.       procedure DeleteAll;
  96.       procedure Free(Item : pointer);
  97.       procedure FreeAll;
  98.       function  IndexOf(Item : pointer) : longint; virtual;
  99.       procedure Insert(Item : pointer); virtual;
  100.       function  Iterate(Action : TIterator; Backwards : boolean;
  101.                         ExtraData : pointer) : pointer;
  102.       procedure Pack;
  103.  
  104.       property Limit : longint
  105.          read GetLimit;
  106.  
  107.       property Items[Index : longint] : pointer
  108.          read At
  109.          write AtPut;
  110.          default;
  111.   end;
  112.  
  113.   TEZSortedCollection = class(TEZCollection)
  114.     public
  115.       function  IndexOf(Item : pointer) : longint; override;
  116.       procedure Insert(Item : pointer); override;
  117.       function  Search(Item : pointer; var Index : longint) : boolean; virtual;
  118.   end;
  119.  
  120.   TEZStringCollection = class(TEZSortedCollection)
  121.     public
  122.       constructor Create(DataOwner : boolean); override;
  123.   end;
  124.  
  125.   TEZStrZCollection = class(TEZSortedCollection)
  126.     public
  127.       constructor Create(DataOwner : boolean); override;
  128.   end;
  129.  
  130. implementation
  131.  
  132. procedure RaiseCollError(Code : integer);
  133.   var
  134.     SCode : integer;
  135.   begin
  136.     case Code of
  137.       coIndexError : SCode := escIndexError;
  138.       coOverflow   : SCode := escTooManyItems;
  139.     end;
  140.     EZDSLSup.RaiseError(SCode);
  141.   end;
  142.  
  143. {===TEZCollection creation/destruction===============================}
  144. constructor TEZCollection.Create(DataOwner : boolean);
  145.   begin
  146.     NodeSize := 0;
  147.     inherited Create(DataOwner);
  148.  
  149.     GrowPageArray(1);
  150.     AddPageItem(0);
  151.   end;
  152. {--------}
  153. constructor TEZCollection.Clone(Source : TAbstractContainer;
  154.                                 DataOwner : boolean; NewCompare : TCompareFunc);
  155.   var
  156.     OldColl : TEZCollection absolute Source;
  157.     NewData : pointer;
  158.     i       : longint;
  159.   begin
  160.     Create(DataOwner);
  161.     Compare := NewCompare;
  162.     DupData := OldColl.DupData;
  163.     DisposeData := OldColl.DisposeData;
  164.  
  165.     if not (Source is TEZCollection) then
  166.       RaiseError(escBadSource);
  167.  
  168.     if not OldColl.IsEmpty then
  169.       for i := 0 to pred(OldColl.Count) do
  170.         begin
  171.           NewData := DupData(OldColl.Items[i]);
  172.           try
  173.             Insert(NewData);
  174.           except
  175.             DisposeData(NewData);
  176.             raise;
  177.           end;
  178.         end;
  179.   end;
  180. {--------}
  181. destructor TEZCollection.Destroy;
  182.   begin
  183.     inherited Destroy;
  184.     if Assigned(PA) then
  185.       begin
  186.         DeletePageItem(0);
  187.         FreeMem(PA, SizeOfPA);
  188.       end;
  189.   end;
  190. {====================================================================}
  191.  
  192.  
  193. {===TEZCollection helper methods=====================================}
  194. procedure TEZCollection.AddPageItem(AtIndex : integer);
  195.   var
  196.     NewPage : PezcPage;
  197.     NewMax  : integer;
  198.   begin
  199.     {$IFDEF DEBUG}
  200.     if (AtIndex > ItemsInPA) then
  201.       raise Exception.Create('Bad AtIndex parm to AddPageItem');
  202.     {$ENDIF}
  203.     if (ItemsInPA = MaxItemsInPA) then
  204.       if (MaxItemsInPA < ezcPageArrayElementCount) then
  205.         begin
  206.           case MaxItemsInPA of
  207.             1 : NewMax := 2;
  208.             2 : NewMax := 4;
  209.             4 : NewMax := 8;
  210.             8 : NewMax := 16;
  211.           else
  212.             NewMax := MaxItemsInPA + 16;
  213.             if (NewMax > ezcPageArrayElementCount) then
  214.               NewMax := ezcPageArrayElementCount;
  215.           end;{case}
  216.           GrowPageArray(NewMax);
  217.         end
  218.       else
  219.         begin
  220.           Pack;
  221.           if (ItemsInPA = ezcPageArrayElementCount) then
  222.             RaiseCollError(coOverflow);
  223.         end;
  224.     GetMem(NewPage, ezcPageElementCount * sizeof(pointer));
  225.     {$IFDEF DEBUG}
  226.     FillChar(NewPage^, ezcPageElementCount * sizeof(pointer), $CC);
  227.     {$ENDIF}
  228.     if (AtIndex < ItemsInPA) then
  229.       Move(PA^[AtIndex], PA^[succ(AtIndex)], (ItemsInPA - AtIndex) * sizeof(TezcPageItem));
  230.     with PA^[AtIndex] do
  231.       begin
  232.         UsedItems := 0;
  233.         Items := NewPage;
  234.       end;
  235.     inc(ItemsInPA);
  236.   end;
  237. {--------}
  238. procedure TEZCollection.DeletePageItem(AtIndex : integer);
  239.   begin
  240.     {$IFDEF DEBUG}
  241.     if (AtIndex >= ItemsInPA) then
  242.       raise Exception.Create('Bad AtIndex parm to DeletePageItem');
  243.     {$ENDIF}
  244.     with PA^[AtIndex] do
  245.       FreeMem(Items, ezcPageElementCount * sizeof(pointer));
  246.     dec(ItemsInPA);
  247.     if (AtIndex < ItemsInPA) then
  248.       Move(PA^[succ(AtIndex)], PA^[AtIndex], (ItemsInPA - AtIndex) * sizeof(TezcPageItem));
  249.   end;
  250. {--------}
  251. function  TEZCollection.GetPageGivenIndex(Index : longint;
  252.                                           var InxInPage : integer) : integer;
  253.   const
  254.     SizeOfPageItem = sizeof(TezcPageItem);
  255.   var
  256.     PageNum    : integer;
  257.     StartIndex : longint;
  258.     GoForward  : boolean;
  259.   begin
  260.     if (Index = CacheIndex) then
  261.       begin
  262.         Result := CachePageNum;
  263.         InxInPage := CacheInxInPage;
  264.         Exit;
  265.       end;
  266.     if (Index < CacheIndex) then
  267.       if ((Index * 2) <= CacheIndex) then
  268.         begin
  269.           {Index is closer to 0 than CacheIndex}
  270.           PageNum := 0;
  271.           StartIndex := Index;
  272.           GoForward := true;
  273.         end
  274.       else
  275.         begin
  276.           {Index is closer to CacheIndex than 0}
  277.           PageNum := CachePageNum;
  278.           StartIndex :=
  279.              (CacheIndex - CacheInxInPage + PA^[CachePageNum].UsedItems) -
  280.              Index;
  281.           GoForward := false;
  282.         end
  283.     else {Index > CacheIndex}
  284.       if (Index - CacheIndex) <= (Count - Index - 1) then
  285.         begin
  286.           {Index is closer to CacheIndex than Count}
  287.           PageNum := CachePageNum;
  288.           StartIndex := Index - (CacheIndex - CacheInxInPage);
  289.           GoForward := true;
  290.         end
  291.       else
  292.         begin
  293.           {Index is closer to Count than CacheIndex}
  294.           PageNum := pred(ItemsInPA);
  295.           StartIndex := Count - Index;
  296.           GoForward := false;
  297.         end;
  298.     {$IFDEF Win32}
  299.     if GoForward then
  300.       asm
  301.         mov edx, Self
  302.         mov edx, [edx].TEZCollection.PA
  303.  
  304.         mov ecx, PageNum      {This assumes sizeof(TezcPageItem)=8}
  305.         mov eax, ecx
  306.         shl eax, 3
  307.         add edx, eax
  308.  
  309.         mov eax, StartIndex
  310.       @@NextPage:
  311.         sub eax, [edx].TezcPageItem.UsedItems
  312.         jl @@FoundIt
  313.         inc ecx
  314.         add edx, SizeOfPageItem
  315.         jmp @@NextPage
  316.       @@FoundIt:
  317.         add eax, [edx].TezcPageItem.UsedItems
  318.         mov edx, InxInPage
  319.         mov [edx], eax
  320.         mov @Result, ecx
  321.       end
  322.     else {go backwards}
  323.       asm
  324.         mov edx, Self
  325.         mov edx, [edx].TEZCollection.PA
  326.  
  327.         mov ecx, PageNum      {This assumes sizeof(TezcPageItem)=8}
  328.         mov eax, ecx
  329.         shl eax, 3
  330.         add edx, eax
  331.  
  332.         mov eax, StartIndex
  333.       @@NextPage:
  334.         sub eax, [edx].TezcPageItem.UsedItems
  335.         jl @@FoundIt
  336.         je @@FoundItAsZero
  337.         dec ecx
  338.         sub edx, SizeOfPageItem
  339.         jmp @@NextPage
  340.       @@FoundIt:
  341.         neg eax
  342.       @@FoundItAsZero:
  343.         mov edx, InxInPage
  344.         mov [edx], eax
  345.         mov @Result, ecx
  346.       end;
  347.     {$ELSE}
  348.     if GoForward then
  349.       asm
  350.         mov si, ds           {SI stores the Delphi data segment}
  351.         lds di, Self
  352.         lds di, [di].TEZCollection.PA
  353.  
  354.         mov cx, PageNum      {This assumes sizeof(TezcPageItem)=6}
  355.         mov ax, cx
  356.         shl ax, 1
  357.         add ax, cx
  358.         shl ax, 1
  359.         add di, ax
  360.  
  361.         xor bx, bx
  362.         mov dx, StartIndex.Word[2]
  363.         mov ax, StartIndex.Word[0]
  364.       @@NextPage:
  365.         sub ax, [di].TezcPageItem.UsedItems
  366.         sbb dx, bx
  367.         jl @@FoundIt
  368.         inc cx
  369.         add di, SizeOfPageItem
  370.         jmp @@NextPage
  371.       @@FoundIt:
  372.         add ax, [di].TezcPageItem.UsedItems
  373.         lds di, InxInPage
  374.         mov [di], ax
  375.         mov ds, si
  376.         mov @Result, cx
  377.       end
  378.     else
  379.       asm
  380.         push ds
  381.         lds di, Self
  382.         lds di, [di].TEZCollection.PA
  383.  
  384.         mov cx, PageNum      {This assumes sizeof(TezcPageItem)=6}
  385.         mov ax, cx
  386.         shl ax, 1
  387.         add ax, cx
  388.         shl ax, 1
  389.         add di, ax
  390.  
  391.         xor bx, bx
  392.         mov dx, StartIndex.Word[2]
  393.         mov ax, StartIndex.Word[0]
  394.       @@NextPage:
  395.         sub ax, [di].TezcPageItem.UsedItems
  396.         sbb dx, bx
  397.         jl @@FoundIt
  398.         mov si, ax
  399.         or si, dx
  400.         je @@FoundItAsZero
  401.         dec cx
  402.         sub di, SizeOfPageItem
  403.         jmp @@NextPage
  404.       @@FoundIt:
  405.         neg ax
  406.       @@FoundItAsZero:
  407.         lds di, InxInPage
  408.         mov [di], ax
  409.         pop ds
  410.         mov @Result, cx
  411.       end;
  412.     {$ENDIF}
  413.     CacheIndex := Index;
  414.     CachePageNum := Result;
  415.     CacheInxInPage := InxInPage;
  416.   end;
  417. {--------}
  418. procedure TEZCollection.GrowPageArray(NewNumElements : integer);
  419.   var
  420.     NewSize : Cardinal;
  421.     NewPA   : PezcPageArray;
  422.   begin
  423.     NewSize := NewNumElements * sizeof(TezcPageItem);
  424.     GetMem(NewPA, NewSize);
  425.     {$IFDEF DEBUG}
  426.     FillChar(NewPA^, NewSize, $CC);
  427.     {$ENDIF}
  428.     if Assigned(PA) then
  429.       begin
  430.         Move(PA^, NewPA^, ItemsInPA * sizeof(TezcPageItem));
  431.         FreeMem(PA, SizeOfPA);
  432.       end;
  433.     PA := NewPA;
  434.     SizeOfPA := NewSize;
  435.     MaxItemsInPA := NewNumElements;
  436.   end;
  437. {--------}
  438. procedure TEZCollection.ValidateIndex(Index : longint);
  439.   begin
  440.     if (Index < 0) or (Index >= Count) then
  441.       RaiseCollError(coIndexError);
  442.   end;
  443. {====================================================================}
  444.  
  445.  
  446. {===TEZCollection item access========================================}
  447. function TEZCollection.At(Index : longint) : pointer;
  448.   var
  449.     PageNum : integer;
  450.     InxInPage : integer;
  451.   begin
  452.     ValidateIndex(Index);
  453.     PageNum := GetPageGivenIndex(Index, InxInPage);
  454.     Result := PA^[PageNum].Items^[InxInPage];
  455.   end;
  456. {--------}
  457. procedure TEZCollection.AtPut(Index : longint; Item : pointer);
  458.   var
  459.     PageNum : integer;
  460.     InxInPage : integer;
  461.   begin
  462.     ValidateIndex(Index);
  463.     PageNum := GetPageGivenIndex(Index, InxInPage);
  464.     PA^[PageNum].Items^[InxInPage] := Item;
  465.   end;
  466. {====================================================================}
  467.  
  468.  
  469. {===TEZCollection property access====================================}
  470. function TEZCollection.GetLimit : longint;
  471.   begin
  472.     Result := longint(MaxItemsInPA) * ezcPageElementCount;
  473.   end;
  474. {====================================================================}
  475.  
  476.  
  477. {===TEZCollection methods============================================}
  478. procedure TEZCollection.Assign(Source : TPersistent);
  479.   var
  480.     Src     : TEZCollection absolute Source;
  481.     NewData : pointer;
  482.     i       : longint;
  483.   begin
  484.     if not (Source is TEZCollection) then
  485.       Exit;
  486.     Empty;
  487.     FIsDataOwner := Src.IsDataOwner;
  488.     Compare := Src.Compare;
  489.     DupData := Src.DupData;
  490.     DisposeData := Src.DisposeData;
  491.     if not Src.IsEmpty then
  492.       for i := 0 to pred(Src.Count) do
  493.         begin
  494.           NewData := DupData(Src.Items[i]);
  495.           try
  496.             Insert(NewData);
  497.           except
  498.             DisposeData(NewData);
  499.           end;
  500.         end;
  501.   end;
  502. {--------}
  503. procedure TEZCollection.AtDelete(Index : longint);
  504.   var
  505.     PageNum : integer;
  506.     InxInPage : integer;
  507.   begin
  508.     ValidateIndex(Index);
  509.     PageNum := GetPageGivenIndex(Index, InxInPage);
  510.     dec(FCount);
  511.     with PA^[PageNum] do
  512.       begin
  513.         dec(UsedItems);
  514.         if (UsedItems = 0) then
  515.           begin
  516.             if (ItemsInPA > 1) then
  517.               DeletePageItem(PageNum);
  518.           end
  519.         else if (InxInPage < UsedItems) then
  520.           Move(Items^[succ(InxInPage)], Items^[InxInPage],
  521.                (UsedItems - InxInPage) * sizeof(pointer));
  522.       end;
  523.     CacheIndex := 0;
  524.     CachePageNum := 0;
  525.     CacheInxInPage := 0;
  526.   end;
  527. {--------}
  528. procedure TEZCollection.AtFree(Index : longint);
  529.   begin
  530.     if IsDataOwner then
  531.       DisposeData(Items[Index]);
  532.     AtDelete(Index);
  533.   end;
  534. {--------}
  535. procedure TEZCollection.AtInsert(Index : longint; Item : pointer);
  536.   const
  537.     HalfPageCount = ezcPageElementCount div 2;
  538.   var
  539.     PageNum : integer;
  540.     InxInPage : integer;
  541.     AddingAtEnd : boolean;
  542.   begin
  543.     {maximum count check}
  544.     if (Count = ezcMaxCount) then
  545.       RaiseCollError(coOverflow);
  546.     {take care of special case-adding at end}
  547.     if (Index = Count) then
  548.       begin
  549.         AddingAtEnd := true;
  550.         PageNum := pred(ItemsInPA);
  551.         InxInPage := PA^[PageNum].UsedItems;
  552.       end
  553.     {otherwise work out where to add it}
  554.     else
  555.       begin
  556.         ValidateIndex(Index);
  557.         AddingAtEnd := false;
  558.         PageNum := GetPageGivenIndex(Index, InxInPage);
  559.       end;
  560.  
  561.     {do we need a new page?}
  562.     if (PA^[PageNum].UsedItems = ezcPageElementCount) then
  563.       begin
  564.         {add a new page after ours}
  565.         AddPageItem(succ(PageNum));
  566.         {if we are adding to the end, patch up the page number and index}
  567.         if AddingAtEnd then
  568.           begin
  569.             PageNum := succ(PageNum);
  570.             InxInPage := 0;
  571.           end
  572.         {if we were not adding at end, split the old page in two for efficiency}
  573.         else
  574.           begin
  575.             Move(PA^[PageNum].Items^[HalfPageCount],
  576.                  PA^[succ(PageNum)].Items^[0],
  577.                  HalfPageCount * sizeof(pointer));
  578.             PA^[PageNum].UsedItems := HalfPageCount;
  579.             PA^[succ(PageNum)].UsedItems := HalfPageCount;
  580.             if (InxInPage >= HalfPageCount) then
  581.               begin
  582.                 dec(InxInPage, HalfPageCount);
  583.                 inc(PageNum);
  584.               end;
  585.           end;
  586.       end;
  587.  
  588.     {insert the item now}
  589.     with PA^[PageNum] do
  590.       begin
  591.         if (InxInPage < UsedItems) then
  592.           Move(Items^[InxInPage], Items^[succ(InxInPage)],
  593.                (UsedItems - InxInPage) * sizeof(pointer));
  594.         Items^[InxInPage] := Item;
  595.         inc(UsedItems);
  596.       end;
  597.     inc(FCount);
  598.     CacheIndex := Index;
  599.     CachePageNum := PageNum;
  600.     CacheInxInPage := InxInPage;
  601.   end;
  602. {--------}
  603. procedure TEZCollection.Delete(Item : pointer);
  604.   var
  605.     Index : longint;
  606.   begin
  607.     Index := IndexOf(Item);
  608.     if (Index <> -1) then
  609.       AtDelete(Index);
  610.   end;
  611. {--------}
  612. procedure TEZCollection.DeleteAll;
  613.   var
  614.     i : integer;
  615.   begin
  616.     for i := pred(ItemsInPA) downto 1 do
  617.       DeletePageItem(i);
  618.     PA^[0].UsedItems := 0;
  619.     FCount := 0;
  620.     CacheIndex := 0;
  621.     CachePageNum := 0;
  622.     CacheInxInPage := 0;
  623.   end;
  624. {--------}
  625. procedure TEZCollection.Empty;
  626.   begin
  627.     FreeAll;
  628.   end;
  629. {--------}
  630. procedure TEZCollection.Free(Item : pointer);
  631.   var
  632.     Index : longint;
  633.   begin
  634.     Index := IndexOf(Item);
  635.     if (Index <> -1) then
  636.       AtFree(Index);
  637.   end;
  638. {--------}
  639. procedure TEZCollection.FreeAll;
  640.   var
  641.     PageNum : integer;
  642.     Inx     : integer;
  643.   begin
  644.     if IsDataOwner then
  645.       for PageNum := 0 to pred(ItemsInPA) do
  646.         for Inx := 0 to pred(PA^[PageNum].UsedItems) do
  647.           DisposeData(PA^[PageNum].Items^[Inx]);
  648.     DeleteAll;
  649.   end;
  650. {--------}
  651. function  TEZCollection.IndexOf(Item : pointer) : longint;
  652.   var
  653.     PageNum : integer;
  654.     Inx     : integer;
  655.   begin
  656.     Result := -1;
  657.     for PageNum := 0 to pred(ItemsInPA) do
  658.       with PA^[PageNum] do
  659.         for Inx := 0 to pred(UsedItems) do
  660.           begin
  661.             inc(Result);
  662.             if (Items^[Inx] = Item) then
  663.               begin
  664.                 CacheIndex := Result;
  665.                 CachePageNum := PageNum;
  666.                 CacheInxInPage := Inx;
  667.                 Exit;
  668.               end;
  669.           end;
  670.     Result := -1;
  671.   end;
  672. {--------}
  673. procedure TEZCollection.Insert(Item : pointer);
  674.   begin
  675.     AtInsert(Count, Item);
  676.   end;
  677. {--------}
  678. function  TEZCollection.Iterate(Action    : TIterator;
  679.                                 Backwards : boolean;
  680.                                 ExtraData : pointer) : pointer;
  681.   var
  682.     PageNum : integer;
  683.     Inx     : integer;
  684.   begin
  685.     if Backwards then
  686.       begin
  687.         for PageNum := pred(ItemsInPA) downto 0 do
  688.           with PA^[PageNum] do
  689.             for Inx := pred(UsedItems) downto 0 do
  690.               if not Action(Self, Items^[Inx], ExtraData) then
  691.                 begin
  692.                   Result := Items^[Inx];
  693.                   Exit;
  694.                 end;
  695.       end
  696.     else
  697.       begin
  698.         for PageNum := 0 to pred(ItemsInPA) do
  699.           with PA^[PageNum] do
  700.             for Inx := 0 to pred(UsedItems) do
  701.               if not Action(Self, Items^[Inx], ExtraData) then
  702.                 begin
  703.                   Result := Items^[Inx];
  704.                   Exit;
  705.                 end;
  706.       end;
  707.     Result := nil;
  708.   end;
  709. {--------}
  710. procedure TEZCollection.Pack;
  711.   var
  712.     FromPage         : integer;
  713.     ToPage           : integer;
  714.     ItemsToGo        : integer;
  715.     ItemsInToPage    : integer;
  716.     ItemsInFromPage  : integer;
  717.     StillPacking : boolean;
  718.   begin
  719.     if (ItemsInPA = 1) then Exit;
  720.     ToPage := -1;
  721.     FromPage := 1;
  722.     StillPacking := true;
  723.     while StillPacking do
  724.       begin
  725.         inc(ToPage);
  726.         ItemsInToPage := PA^[ToPage].UsedItems;
  727.         ItemsToGo := ezcPageElementCount - ItemsInToPage;
  728.         if (FromPage <= ToPage) then
  729.           begin
  730.             FromPage := succ(ToPage);
  731.             if (FromPage = ItemsInPA) then
  732.               StillPacking := false;
  733.           end;
  734.         while StillPacking and (ItemsToGo > 0) do
  735.           begin
  736.             ItemsInFromPage := PA^[FromPage].UsedItems;
  737.             if (ItemsInFromPage <= ItemsToGo) then
  738.               begin
  739.                 Move(PA^[FromPage].Items^[0], PA^[ToPage].Items^[ItemsInToPage],
  740.                      ItemsInFromPage * sizeof(pointer));
  741.                 inc(ItemsInToPage, ItemsInFromPage);
  742.                 PA^[ToPage].UsedItems := ItemsInToPage;
  743.                 dec(ItemsToGo, ItemsInFromPage);
  744.                 PA^[FromPage].UsedItems := 0;
  745.                 inc(FromPage);
  746.                 if (FromPage = ItemsInPA) then
  747.                   StillPacking := false;
  748.               end
  749.             else
  750.               begin
  751.                 Move(PA^[FromPage].Items^[0], PA^[ToPage].Items^[ItemsInToPage],
  752.                      (ItemsToGo * sizeof(pointer)));
  753.                 PA^[ToPage].UsedItems := ezcPageElementCount;
  754.                 Move(PA^[FromPage].Items^[ItemsToGo], PA^[FromPage].Items^[0],
  755.                      (ItemsInFromPage - ItemsToGo) * sizeof(pointer));
  756.                 PA^[FromPage].UsedItems := ItemsInFromPage - ItemsToGo;
  757.                 ItemsToGo := 0;
  758.               end
  759.           end;
  760.       end;
  761.     if (ToPage < pred(ItemsInPA)) then
  762.       begin
  763.         for FromPage := pred(ItemsInPA) downto succ(ToPage) do
  764.           DeletePageItem(FromPage);
  765.         GrowPageArray(ItemsInPA);
  766.       end;
  767.     CacheIndex := 0;
  768.     CachePageNum := 0;
  769.     CacheInxInPage := 0;
  770.   end;
  771. {====================================================================}
  772.  
  773.  
  774. {====================================================================}
  775. function  TEZSortedCollection.IndexOf(Item : pointer) : longint;
  776.   var
  777.     Index : longint;
  778.   begin
  779.     if Search(Item, Index) then
  780.       Result := Index
  781.     else
  782.       Result := -1;
  783.   end;
  784. {--------}
  785. procedure TEZSortedCollection.Insert(Item : pointer);
  786.   var
  787.     Index : longint;
  788.   begin
  789.     if not Search(Item, Index) then
  790.       AtInsert(Index, Item)
  791.     else
  792.       RaiseError(escInsertDup);
  793.   end;
  794. {--------}
  795. function  TEZSortedCollection.Search(Item : pointer; var Index : longint) : boolean;
  796.   var
  797.     L, R, M   : longint;
  798.     PageNum   : integer;
  799.     InxInPage : integer;
  800.     CompResult : integer;
  801.   begin
  802.     {check the obvious case}
  803.     if (Count = 0) then
  804.       begin
  805.         Result := false;
  806.         Index := 0;
  807.         Exit;
  808.       end;
  809.     {standard binary search: Algorithms by Sedgewick}
  810.     L := 0;
  811.     R := pred(Count);
  812.     repeat
  813.       M := (L + R) div 2;
  814.       PageNum := GetPageGivenIndex(M, InxInPage);
  815.       CompResult := Compare(Item, PA^[PageNum].Items^[InxInPage]);
  816.       if (CompResult = 0) then
  817.         begin
  818.           Result := true;
  819.           Index := M;
  820.           Exit;
  821.         end
  822.       else if (CompResult < 0) then
  823.         R := M - 1
  824.       else
  825.         L := M + 1;
  826.     until (L > R);
  827.     Result := false;
  828.     if (CompResult > 0) then
  829.       Index := M + 1
  830.     else
  831.       Index := M;
  832.   end;
  833. {====================================================================}
  834.  
  835. {===TEZStringCollection==============================================}
  836. constructor TEZStringCollection.Create(DataOwner : boolean);
  837.   begin
  838.     inherited Create(DataOwner);
  839.     Compare := EZStrCompare;
  840.     DupData := EZStrDupData;
  841.     DisposeData := EZStrDisposeData;
  842.   end;
  843. {====================================================================}
  844.  
  845. {===TEZStrZCollection================================================}
  846. constructor TEZStrZCollection.Create(DataOwner : boolean);
  847.   begin
  848.     inherited Create(DataOwner);
  849.     Compare := EZStrZCompare;
  850.     DupData := EZStrZDupData;
  851.     DisposeData := EZStrZDisposeData;
  852.   end;
  853. {====================================================================}
  854.  
  855. end.
  856.